⟸ Go Back ⟸

Exercise 8 (Homework 1).

(theory of languages, cardinality of languages)

On the size of languages

Justify your answers to the following questions.

1. Given two languages L_1,L_2, is it true that |L_1|\cdot|L_2|=|L_1\cdot L_2|? What if L_1=L_2?
2. Given a homomorphism \sigma, is it true that if \sigma is injective then |\sigma(L)|=|L|?
3. Given a language L, is it true that |L^R|=|L|?
4. Given a language L and a positive integer n, is it true that |L^n|=|L|^n?

Recall that a function f is injective if f(x)=f(y) implies x=y.